The invention relates to a method and devices for reducing multimedia data compression/encoding time, and in particular, to methods and devices for avoiding access to zero values in a frequency domain region.
With the improvement of signal detection and processing techniques, still images, video, and audio data can be preserved, processed, transmitted in electronic formats (especially in digital formats) in high fidelity. Generally, multimedia files are quite large, thus requiring compression before storage and transmission. Accordingly, compressed multimedia data must be decompressed before display. Compression of multidimensional image data (such as 2-dimensional images and/or time-domain changes) is particularly resource consumptive. Hence, compressing image data with high efficiency and low cost has become a significant issue.
FIG. 1 is a flowchart of conventional image compression (data compression), such as Motion Picture Expert Group (MPEG) compression. As shown in FIG. 1, a motion image data M (such as a movie or an animation) may be treated as a series of static pictures A1, A2, A3, A5, and others, displayed sequentially to simulate motion. To achieve a high compression ratio, compression of the video data comprises detecting differences between the static pictures (intra-coding) in step 10, and encoding frames (inter-coding) in step 12.
There may be little difference between frames of a video clip simulating continuous motion. For example, sequential display of the pictures A1, A2, and A3 in FIG. 1 simulates motion of an object Oj moving against background Bk, wherein there is no perceptible difference in the pictures A1, A2, and A3 except the object Oj. In step 10, a motion detection operation may be performed to detect differences between frames. For example, that object Oj in FIG. 1 moves and background Bk is still may be recognized by detecting the pictures A1 and A2. Additionally, vector V12 is derived to represent the movement direction and distance of traveled by the object Oj. Put simply, the object Oj in the picture A1 is moved along with the vector V12 (known as motion compensation) to yield a predicted image P2 (not shown in FIG. 1) to simulate the picture A2. Predicted the picture P2 is, however, only a prediction of the picture A2, and may not precisely match the picture A2. For example, reflected areas of light on the object Oj may differ between the pictures A1 and A2. The difference between the predicted image P2 and the picture A2 is assumed to be imperceptible, and the picture A2 is subtracted by the predicted image P2 to yield difference image D12. Thus, the frame comprising the picture A2 may be generated by motion compensating the picture A1 and adding the difference image D12 to the compensated picture A1. Thus, the picture A1, vector V12, and image D12 can represent the pictures A1 and A2. Image D12 may comprise little data as long as the difference between the predicted image P2 and the picture A2 is small, facilitating a high compression ratio of the pictures A1 and A2.
Similarly, the picture A3 in FIG. 1 may be presented utilizing the picture A2, vector V23, and image D23. The picture A1, images D12, D23, vector V12, and V23 simulate a portion of video M comprising the pictures A1, A2, and A3, whereby compressing the portion of video M accordingly. The video M may comprise completely irrelevant portions. For example, the pictures A4 and A5 simulate motion of other objects moving in another background, so the picture A3 may be quite different from the picture A4. Motion detection is applied to the pictures A4 and A5 instead of A3 and A4 to compress the portion of video M comprising the pictures A4 and A5 in step 10.
After intra-encoding in step 10, pictures, such as the pictures A1 and A4 in FIG. 1, and difference images, such as the image D12, D23, and D45 are respectively encoded/compressed in step 12 to enhance compression ratio. The detailed procedures of step 12 are shown in FIG. 2. When compressed, a pictures A, such as the pictures A1, A4, the images D12, or D23, is first fragmented into blocks B each comprising pixels Bij. 2-dimensional frequency domain transformation, such as Discrete Cosine Transform (DCT), is applied to each block B to generate array C comprising elements Cij representing frequency values of block B. Elements Qij generated from quantization of the elements Cij comprise quantized array Q which is a frequency domain array. The elements Qij of the 2-dimensional array Q are rearranged to an one-dimensional array S in a specific order, this procedure is known as a sequential scan. Run-length encoding is applied to the array S to generate another array R. Huffman encoding is applied to array R to generate array H, and compression of the picture A is complete.
In step 12, because a block B comprises a small portion of the picture A, pixels Bij therein may have approximately the same value. After a block B has been transformed to frequency domain and quantized, most high frequency elements Cij and Qij have a zero value (or have an approximately zero value). In other words, arrays C and Q are sparse arrays. Elements Sk of the array S, each representing a Qij, may also comprise a plurality of zero values. Zero values between non-zero elements Sk are encoded to shorten the length thereof during the run-length encoding of array S to shorten the length thereof. For example, in a case wherein 10 zero values exist between non-zero elements Si and Sj, element Sj may be encoded to represent and replace the actual 10 zero values. Thus, the length of the array R generated by run-length encoding the array S is shortened. The length of the array H is further shortened after Huffman encoding of the array R. A plurality of the arrays R generated from compressing all blocks B comprise compressed multimedia data, the result of compressing the picture A.
When compressing a still image (such as JPEG compression), step 12 may be performed directly to omit step 10.
FIG. 3 is a block diagram of conventional image compression/decompression circuits. The processing circuit 300 compresses/encodes image data and comprises a central processing unit (CPU) 302, a memory access module 304, a dynamic estimation module 306, a frequency domain transformation/quantization module 308, a scan control module 310, and an internal memory 312 (such as random access memories). The CPU 302 controls all operations of the processing circuit 300. The Memory access module 304 is capable of direct memory access (DMA) and enables the processing circuit 300 to access an external storage 350 directly, for example, to import a compression source therefrom. The dynamic estimation module 306 may perform dynamic estimation in step 10. The frequency domain transformation/quantization module 308 may perform frequency domain transformation and quantization in step 12. The internal memory 312 temporarily stores data processed by the processing circuit 300.
For example, when the processing circuit 300 compressing (encoding) image data, the frequency domain transformation/quantization module 308 transforms and quantizes blocks B of each frame to generate the 2-dimensional array Q, and elements Qij therein are written into the internal memory 312 and then read by the scan control module 310 when a sequential scan is performed to generate the array S. The subsequent steps are then performed accordingly.
Thus, the processing circuit 300 frequently accesses the internal memory 312. One video clip may comprise a plurality of pictures A which correspond to a plurality of arrays Q representing blocks B thereof. Elements Qij are stored to the internal memory 312 when the processing circuit 300 compresses image data and are read therefrom during a sequential scan. As previously described, an array Q may be a sparse array most elements Qij of which are zero values, so that the length of the array S may be reduced by run-length encoding. The array R records the number of instances of zero pixel values rather than the actual pixels with a zero value, without taking advantage of the properties of the sparse array. It is time consuming, however, to process and access the elements Qij one by one when the processing circuit 300 performs sequential scanning. Thus image compression is time consuming, and the cost is still high if processing circuit 300 is provided with higher bandwidth internal memory to increase the rate of compression.